{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python Optimizations: String Interning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python will automatically intern *certain* strings.\n",
    "\n",
    "In particular all the identifiers (variable names, function names, class names, etc) are interned (singleton objects created).\n",
    "\n",
    "Python will also intern string literals that look like identifiers.\n",
    "\n",
    "For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1342722069536\n",
      "1342722069536\n"
     ]
    }
   ],
   "source": [
    "a = 'hello'\n",
    "b = 'hello'\n",
    "print(id(a))\n",
    "print(id(b))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But not the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1342722047024\n",
      "1342722170928\n"
     ]
    }
   ],
   "source": [
    "a = 'hello, world!'\n",
    "b = 'hello, world!'\n",
    "print(id(a))\n",
    "print(id(b))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "However, because the following literals resemble identifiers, even though they are quite long, Python will still automatically intern them:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1342722047856\n",
      "1342722047856\n"
     ]
    }
   ],
   "source": [
    "a = 'hello_world'\n",
    "b = 'hello_world'\n",
    "print(id(a))\n",
    "print(id(b))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And even longer:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1342721886784\n",
      "1342721886784\n"
     ]
    }
   ],
   "source": [
    "a = '_this_is_a_long_string_that_could_be_used_as_an_identifier'\n",
    "b = '_this_is_a_long_string_that_could_be_used_as_an_identifier'\n",
    "print(id(a))\n",
    "print(id(b))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Even if the string starts with a digit:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1342722046256\n",
      "1342722046256\n"
     ]
    }
   ],
   "source": [
    "a = '1_hello_world'\n",
    "b = '1_hello_world'\n",
    "print(id(a))\n",
    "print(id(b))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That was interned (pointer is the same), but look at this one:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1342722046832\n",
      "1342722172592\n"
     ]
    }
   ],
   "source": [
    "a = '1 hello world'\n",
    "b = '1 hello world'\n",
    "print(id(a))\n",
    "print(id(b))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Interning strings (making them singleton objects) means that testing for string equality can be done faster by comparing the memory address:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a==b: True\n",
      "a is b: True\n"
     ]
    }
   ],
   "source": [
    "a = 'this_is_a_long_string'\n",
    "b = 'this_is_a_long_string'\n",
    "print('a==b:', a == b)\n",
    "print('a is b:', a is b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### <font color=\"orange\">Note: Remember, using `is` ONLY works if the strings were interned!</font>\n",
    "\n",
    "Here's where this technique fails:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a==b: True\n",
      "a is b: False\n"
     ]
    }
   ],
   "source": [
    "a = 'hello world'\n",
    "b = 'hello world'\n",
    "print('a==b:', a==b)\n",
    "print('a is b:', a is b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You *can* force strings to be interned (but only use it if you have a valid performance optimization need):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import sys"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1342722172080\n",
      "1342722172080\n",
      "1342722174896\n"
     ]
    }
   ],
   "source": [
    "a = sys.intern('hello world')\n",
    "b = sys.intern('hello world')\n",
    "c = 'hello world'\n",
    "print(id(a))\n",
    "print(id(b))\n",
    "print(id(c))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice how `a` and `b` are pointing to the same object, but `c` is **NOT**.\n",
    "\n",
    "So, since both `a` and `b` were interned we can use `is` to test for equality of the two strings:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a==b: True\n",
      "a is b: True\n"
     ]
    }
   ],
   "source": [
    "print('a==b:', a==b)\n",
    "print('a is b:', a is b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, does interning really make a big speed difference?\n",
    "\n",
    "Yes, but only if you are performing a *lot* of comparisons."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's run some quick and dirty benchmarks:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def compare_using_equals(n):\n",
    "    a = 'a long string that is not interned' * 200\n",
    "    b = 'a long string that is not interned' * 200\n",
    "    for i in range(n):\n",
    "        if a == b:\n",
    "            pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def compare_using_interning(n):\n",
    "    a = sys.intern('a long string that is not interned' * 200)\n",
    "    b = sys.intern('a long string that is not interned' * 200)\n",
    "    for i in range(n):\n",
    "        if a is b:\n",
    "            pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "equality:  2.965451618090112\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "\n",
    "start = time.perf_counter()\n",
    "compare_using_equals(10000000)\n",
    "end = time.perf_counter()\n",
    "\n",
    "print('equality: ', end-start)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "identity:  0.28690104431129626\n"
     ]
    }
   ],
   "source": [
    "start = time.perf_counter()\n",
    "compare_using_interning(10000000)\n",
    "end = time.perf_counter()\n",
    "\n",
    "print('identity: ', end-start)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see, the performance difference, especially for long strings, and for many comparisons, can be quite radical!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
